//给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。 
//
// 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,2,3,1]
//输出：2
//解释：
//输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
//连续子数组里面拥有相同度的有如下所示：
//[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
//最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,2,3,1,4,2]
//输出：6
//解释：
//数组的度是 3 ，因为元素 2 重复出现 3 次。
//所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
// 
//
// 
//
// 提示： 
//
// 
// nums.length 在 1 到 50,000 范围内。 
// nums[i] 是一个在 0 到 49,999 范围内的整数。 
// 
//
// Related Topics 数组 哈希表 👍 483 👎 0

//数组的度
package leetcode.editor.cn;

import java.util.ArrayList;

class P697DegreeOfAnArray {
    public static void main(String[] args) {
        Solution solution = new P697DegreeOfAnArray().new Solution();
        int[] nums = {1, 2, 2, 3, 1};
        int count = solution.findShortestSubArray(nums);
        System.out.println(count);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findShortestSubArray(int[] nums) {
            int[] counts = new int[50000];
            Integer[] firstIndex = new Integer[50000];
            int[] lastIndex = new int[50000];

            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                //num位置 计数
                counts[num]++;
                //num首次出现的位置 记一次即可
                if (firstIndex[num] == null) {
                    firstIndex[num] = i;
                }
                //num最后一次出现的位置 持续更新
                lastIndex[num] = i;
            }

            //找出频数最大的次数是多少
            int maxCount = 0;
            for (int count : counts) {
                maxCount = Math.max(maxCount, count);
            }

            //最高的频次可能出现多次
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < counts.length; i++) {
                if (counts[i] == maxCount) {
                    list.add(i);
                }
            }
            //最高频次数
            int minLength = Integer.MAX_VALUE;
            for (Integer i : list) {
                //System.out.println("i: " + i);
                //System.out.println("lastIndex[i]: " + lastIndex[i]);
                //System.out.println("firstIndex[i]: " + firstIndex[i]);
                //System.out.println("lastIndex[i] - firstIndex[i]: " + (lastIndex[i] - firstIndex[i]));
                minLength = Math.min(minLength, lastIndex[i] - firstIndex[i]);
            }
            return minLength + 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}